/*
 * AlphaBetaBackgammonAgent.java
 * CMPT 310 - Assignment 2 - Part 2
 * The following file represents a program written in Java
 *  programming language. The file describes a class that is used to
 *  perform alphabeta search for backgammon game.
 */

package bkgm;

/**
 *
 * @author: Andriy Baranskyy, Egor Chalubeyeu
 *email: abaransk@sfu.ca and egorc@sfu.ca
 */

import org.omg.CORBA.DATA_CONVERSION;
import org.w3c.dom.Text;
public class AlphaBetaBackgammonAgent extends BackgammonAgent {
    private Evaluation evaluation;
    private int otherPlayerNum; //stores the opponent number
    final int depthOfGameTree=3; //how deep down the rabbit hole do we go?, 3 for 2-ply
    private int highestLevelReached=0; //highest level of the tree reached so far for tree printing purposes
    String[] treeVisualisation;//to print out the tree
    final boolean PRINTTREE=false;//decide whether to print the tree
    final int MAXNODE = 0;
    final int MINCHANCENODE = 1;
    final int MINNODE = 2;
    final int MAXCHANCENODE = 3;
    final Float p1 = (new Float(2.0F/(new Float(Dice.DIE_MAX*Dice.DIE_MAX))));//for rolls like i,j, where i!=j
    final Float p2 = (new Float(1.0F/(new Float(Dice.DIE_MAX*Dice.DIE_MAX))));//for rolls with i=j
    private int currentDepth = 0;


    public AlphaBetaBackgammonAgent(int my_player_num) {
	super(my_player_num);
	evaluation = new NaiveEvaluation();
        otherPlayerNum = 1 - player_num; //set player number
    }

    public AlphaBetaBackgammonAgent(int my_player_num, Evaluation e) {
	super(my_player_num);
	evaluation = e;
        otherPlayerNum = 1 - player_num; //set player number
    }

    public Move chooseMove(BackgammonBoard b) {
        //required for tree graphing: highest level reached in the tree(lowest)
        highestLevelReached = 0;
        //initialize tree string
        treeVisualisation = new String[depthOfGameTree+2];
        for (int i=0; i<depthOfGameTree+2; i++)
            treeVisualisation[i] = new String();
        //receive the set of valid moves, get alphabeta to give index of the correct move to make
        MoveSet ms= b.getValidMoves(player_num);
        return ms.getMove(alphabeta(b, depthOfGameTree));
    }
    
    private int alphabeta(BackgammonBoard b, int depth){
        //Store return values(index and max) in DataContainer
        DataContainer d = new DataContainer(maxvalue(b, new Float(0), new Float(15), depth, MAXNODE, -1));
        System.out.println("maxVaue: " + d.getValue());
        //Display tree
        if(this.PRINTTREE)
            this.visualiseTree();
        System.out.println("valid moves were:");
        for (int i=0; i<(b.getValidMoves(player_num).getSize()); i++){
            System.out.println(b.getValidMoves(player_num).getMove(i));
        }
        System.out.println("chosen move n=" + d.getIndex());
        
        return d.getIndex();
    }
    
// maxvalue function: returns max value.
    private DataContainer maxvalue(BackgammonBoard b, Float alpha, Float beta, int depth, int nodeType, int index) {
        //Sanity check
        if (nodeType!=MAXNODE&&nodeType!=MAXCHANCENODE){
            System.err.println("Wrong type of node passed to maxValue");
            System.exit(1);
        }

        //Tree visualization
        if(this.PRINTTREE)
            this.openBracket(this.depthOfGameTree-depth + 1);
        
        //Reached Max depth or cut off due to a win here
        if ((depth == 0)||(b.hasWon(player_num))){ 
            DataContainer rVal = new DataContainer(index, evaluation.boardScore(b,player_num));
            if(this.PRINTTREE)
            {
                this.printValue(this.depthOfGameTree-depth + 1, "rVal" ,rVal.getValue());
            }

            return rVal;
        }
        //if called at chance node, generate possible dice rolls, search through them
        if (nodeType ==MAXCHANCENODE){
            int k = 1;
            float v = 0f;
            float p = 1f;
            BackgammonBoard newBoard;
            //generating dice rolls
            for (int i=1; i<Dice.DIE_MAX+1; i++){
                for (int j=i; j<Dice.DIE_MAX+1; j++){
                    if (i!=j) {
                        //clone the board
                        newBoard = (BackgammonBoard)(b.clone());
                        //set dice
                        newBoard.dc1 = i;
                        newBoard.dc2 = j;
                        v = v + maxvalue(newBoard, alpha/p1, beta/p1, depth-1, MAXNODE, k-1).getValue()*p1;
                        p = p - p1;
                        //prune condition: based on upperbound of the evaluation function and nodes visited so far
                        // if no pruning occurs, expected value will be returned like in minimax
                        if ((p*evaluation.MAX_SCORE<=alpha - v)){
                            if(this.PRINTTREE)
                                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),(v + 0.0001f));
                            return new DataContainer(-1, (v + 0.0001f));
                            }
                        k++;
                    }
                }
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.dc1 = i;
                newBoard.dc2 = i;
                v = v + maxvalue(newBoard, alpha/p2, beta/p2, depth-1, MAXNODE, k-1).getValue()*p2;
                p = p - p2;
                //prune condition: based on upperbound of the evaluation function and nodes visited so far
                // if no pruning occurs, expected value will be returned like in minimax
                if ((p*evaluation.MAX_SCORE<=alpha - v)&&!(i==Dice.DIE_MAX)){
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + Float.toString(alpha) + " b=" + Float.toString(beta) ,v + new Float(0.0001f));
                    return new DataContainer(-1, (v + new Float(0.0001f)));
                }
                k++;
            }
            DataContainer rVal = new DataContainer(-1, v);
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + Float.toString(alpha) + " b=" + Float.toString(beta) ,rVal.getValue());

            return rVal;
        }
        //This is a Maxnode
        else {
            MoveSet ms= b.getValidMoves(this.player_num);
            DataContainer v = new DataContainer(-1, evaluation.MIN_SCORE);
            BackgammonBoard newBoard;
            DataContainer data;
            DataContainer tmp;
            for (int i=0; i<ms.getSize(); i++){
                //for every move generate a board
                newBoard = (BackgammonBoard)(b.clone());       
                //and apply the move
                newBoard.applyMove(player_num,ms.getMove(i));
                //if game over we keep looking for better way to win the game
                if (newBoard.hasWon(player_num))
                    v.setTo(new DataContainer(i, evaluation.boardScore(b,player_num)));
                else{
                    tmp = minvalue(newBoard, alpha, beta, depth-1, MINCHANCENODE, i);
                    if (tmp.getValue()>v.getValue())
                        v.setTo(i,tmp.getValue());
                    else
                        v.setTo(v.getIndex(),v.getValue());
                }
                //prune condition
                if (v.getValue()>=beta) {
                    v.setTo(i, v.getValue());
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3), v.getValue());
                    return v;
                }
                alpha = max(alpha, v);
            }
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),v.getValue());            
            return v;
        }
    }
    private DataContainer minvalue(BackgammonBoard b, Float alpha, Float beta, int depth, int nodeType, int index) {
        //Sanity check
        if (nodeType!=MINCHANCENODE&&nodeType!=MINNODE){
            System.err.println("Wrong type of node passed to minValue");
            System.exit(1);
        }

        //Tree visualization
        if(this.PRINTTREE)
        {
            this.openBracket(this.depthOfGameTree-depth + 1);
        }         
        
        //Depth cutoff/win check
        if ((depth == 0)||(b.hasWon(otherPlayerNum))) {
            DataContainer rVal = new DataContainer(index, evaluation.boardScore(b,otherPlayerNum));
            if(this.PRINTTREE)
            {
                this.printValue(this.depthOfGameTree-depth + 1, "rVal:", rVal.getValue());
            }
            return rVal;
        }
        //if this is a chance node
        if (nodeType == MINCHANCENODE){
            int k = 1;
            BackgammonBoard newBoard;
            float v = 0f;
            float p = 1f;
            //generate chance paths
            for (int i=1; i<Dice.DIE_MAX+1; i++){
                for (int j=i; j<Dice.DIE_MAX+1; j++){
                    if (i!=j) {
                        //clone the board and set the dice
                        newBoard = (BackgammonBoard)(b.clone());
                        newBoard.dc1 = i;
                        newBoard.dc2 = j;
                        v = v + minvalue(newBoard, alpha/p1, beta/p1, depth-1, MINNODE, k-1).getValue()*p1;
                        p = p - p1;
                        //prune condition based on nodes visited so far and lower bound for evaluation fn
                        // if no pruning occurs, expected value will be returned like in minimax
                        if ((p*evaluation.MIN_SCORE>=beta - v)){
                            if(this.PRINTTREE)
                                this.printValue(this.depthOfGameTree-depth + 1, "pruned" ,v - new Float(0.0001f));
                                return new DataContainer(k-1, (v - new Float(0.0001f)));
                        }
                        k++;
                    }
                }
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.dc1 = i;
                newBoard.dc2 = i;
                v = v + minvalue(newBoard, alpha/p2, beta/p2, depth-1, MINNODE, k-1).getValue()*p2;
                p = p - p2;
                if ((p*evaluation.MIN_SCORE>=beta - v)&&(i!=Dice.DIE_MAX)){
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "pruned" ,v - new Float(0.0001f));
                    return new DataContainer(k, (v - new Float(0.0001f)));
                }
                k++;
            }
            DataContainer rVal = new DataContainer(-1, v);
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3) ,rVal.getValue());

            return rVal;
        }
        else {         
            
            MoveSet ms= b.getValidMoves(this.otherPlayerNum);
            BackgammonBoard newBoard;
            DataContainer v = new DataContainer(-1, evaluation.MAX_SCORE);
            DataContainer tmp;
            for (int i=0; i<ms.getSize(); i++){
                newBoard = (BackgammonBoard)(b.clone());
                newBoard.applyMove(otherPlayerNum,ms.getMove(i));
                //pruning condition
                if (newBoard.hasWon(otherPlayerNum))
                    v.setTo(new DataContainer(i, evaluation.boardScore(b,otherPlayerNum)));
                else{
                    tmp = maxvalue(newBoard, alpha, beta, depth-1, MAXCHANCENODE, i);
                    if (tmp.getValue()<v.getValue())
                        v.setTo(i,tmp.getValue());
                    else
                        v.setTo(v.getIndex(),v.getValue());
                 }                
                
                if (v.getValue()<=alpha) {
                    if(this.PRINTTREE)
                        this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3), v.getValue());
                    return v;
                }
                beta = min(beta, v);
            }
            if(this.PRINTTREE)
                this.printValue(this.depthOfGameTree-depth + 1, "a=" + formatFloat(alpha,3,3) + " b=" + formatFloat(beta,3,3),v.getValue());
            return v;
        }
    }
    //compares DataContainer value and float returns bigger value
     public Float max(Float a, DataContainer b){
        if (a>b.getValue()) return a;
        else return b.getValue();
    }
    //compares DataContainer value and float returns smaller value
    public Float min(Float a, DataContainer b){
        if (a<b.getValue()) return a;
        else return b.getValue();
    } 
    
//The functions below are only used for tree printing
    // for tree printing, needs to be called whenever we enter a node
    private void openBracket(int currentLevel)
    {
        if(currentLevel>this.highestLevelReached)
        {
            this.treeVisualisation[currentLevel]="";
            this.highestLevelReached=currentLevel;
        }
        if(this.treeVisualisation[currentLevel-1].length()-1>this.treeVisualisation[currentLevel].length())
        {
            int difference=this.treeVisualisation[currentLevel].length();
            for(int i=0;i<((this.treeVisualisation[currentLevel-1]).length()-difference-1);i++)
            {
                this.treeVisualisation[currentLevel]+=" ";
            }
        }
        this.treeVisualisation[currentLevel]+="(";
        
    }
    // for tree printing, needs to be called whenever we exit a node
    private void printValue(int currentLevel, String text,float value)
    {   
        String toBeAdded=addSpaces(text, 30) + " rVal="+ formatFloat(value,2,1) + ")";
        int lengthToBeAdded=toBeAdded.length();
        if(((this.treeVisualisation[currentLevel].length()-lengthToBeAdded)>0)&&this.treeVisualisation[currentLevel].charAt(this.treeVisualisation[currentLevel].length()-1)!='(')
        {
                this.treeVisualisation[currentLevel]=this.treeVisualisation[currentLevel].substring(0,(this.treeVisualisation[currentLevel].length()-lengthToBeAdded));
        }
        this.treeVisualisation[currentLevel]+=toBeAdded;
        for(int i=1;i<currentLevel;i++)
        {
            int length=this.treeVisualisation[i].length();
            for(int y=0;y<(this.treeVisualisation[currentLevel].length()-length);y++)
                this.treeVisualisation[i]+=" ";
        }
    }

    //formats a string by making it "length" in length by adding spaces
    public String addSpaces(String s, int length){
        String rVal = new String();
        for (int i=s.length(); i<=length;i++) rVal = rVal + " ";
        return rVal + s;
    }
    //formats float by adding spaces on the right and left
    public String formatFloat(float f, int left, int right){
        String tmp = new String(Float.toString(f));
        int z = tmp.indexOf(".");
        String s = new String();
        for (int i = 0; i<=left; i++)
        {   
            if (z-i>=0) s = tmp.substring(z-i,z-i+1) + s;
            else s = " " + s;   
        }
        for (int i = 1; i<=right; i++)
        {   
            if (z+i<tmp.length()) s = s + tmp.substring(z+i,z+i+1) ;
            else s = s + " ";
            
        }
        return s;
    }
    //Prints out the tree array
    private void visualiseTree()
    {
        System.out.println("\nHere is the decision tree:\n");
        for(int i=1;i<=this.highestLevelReached;i++)
        {
            System.out.println(this.treeVisualisation[i]);
        }
        System.out.println();
    }
    
public static void main(String[] args) {
    
	/* Start up a backgammon game using these two agents. */
	BackgammonAgent agent0 = new UserBackgammonAgent(0);
	BackgammonAgent agent1 = new AlphaBetaBackgammonAgent(1);
        //BackgammonAgent agent1 = new SimpleBackgammonAgent(1);

        BackgammonGame bg = new BackgammonGame(agent0,agent1,System.out);
        bg.playGame();
    }
}